package leetcode.hot100;

public class Solution42 {
    //接雨水

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(new Solution42().trap(height));
    }


    public int trap(int[] height) {
        //需要求得[0,i],[i,end]的最大值,i=1...end-1
        int len = height.length;
        if(len<=2) return 0;

        int[] maxFromLeft = new int[len];
        maxFromLeft[0] = height[0];
        for (int i = 1; i < len-1; i++) {
            maxFromLeft[i] = height[i]>maxFromLeft[i-1]?height[i]:maxFromLeft[i-1];
        }

        int maxFromRight = height[len-1], sum = 0, cur = 0;
        for (int i = len-1; i > 0 ; i--) {
            //当前位置能接的雨水高度等于min(左边最大，右边最大)-当前位置高度
            cur = Math.min(maxFromLeft[i],maxFromRight)-height[i];
            sum += cur>0?cur:0;
            //更改从右边数来的最大值
            maxFromRight = height[i]>maxFromRight?height[i]:maxFromRight;
        }
        return sum;
    }
}
